package com.myc.subjects.linkedlist;

import com.myc.subjects.utils.LinkedListUtils;

import java.util.List;

/**
 * Leetcode题号：206
 *
 * 反转链表
 *
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *
 * 示例 1：
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 *
 * 示例 2：
 * 输入：head = [1,2]
 * 输出：[2,1]
 *
 * 示例 3：
 * 输入：head = []
 * 输出：[]
 *
 * 提示：
 * 链表中节点的数目范围是 [0, 5000]
 * -5000 <= Node.val <= 5000
 *
 * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Fanzhuanlianbiao {
    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(5);
        ListNode listNode4 = new ListNode(4, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        LinkedListUtils.showLinkedList(listNode1);

        Fanzhuanlianbiao fanzhuanlianbiao = new Fanzhuanlianbiao();

        LinkedListUtils.showLinkedList(fanzhuanlianbiao.reverseList2(listNode1));

    }

    /**
     * 方法一：迭代
     * 时间复杂度：O(n)
     * 通过临时记录后一个指针的方式进行迭代
     */
    public ListNode reverseList1(ListNode head) {

        ListNode curr = head;//当前节点
        ListNode prev = null;//每次迭代需要记录前一个节点，因为需要将指针指回来

        while(curr != null){
            //临时记录下一个节点，是为了在指针指回去之后还能继续遍历
            ListNode tempNext = curr.next;
            curr.next = prev;

            //向后移动 prev 和 curr 两个指针
            prev = curr;
            curr = tempNext;
        }

        //最后的头结点停留在prev指针的位置
        return prev;
    }

    /**
     * 方法二：递归
     * 时间复杂度：O(n)
     * 先处理边界情况，同时也是递归终止条件,这里处理最后一侧操作，以及最终返回值的最初形态，这一题的返回值的形态一直不变，都是最后一个节点，所以不需要处理，直接返回
     * 判断递归操作出现的位置，在递归操作前的代码都是层层深入的时候的操作（关于递归参数值的形态变化操作都在递归前处理），递归操作后的代码都是层层浅出时的操作（关于最终返回值的形态变化操作可以在递归后处理）
     * 递归操作需要将返回值保存下来再处理
     * 最终返回返回值的最终形态
     */
    public ListNode reverseList2(ListNode head) {

        //1.处理特殊情况，同时也是递归终止条件
        if(head == null || head.next == null) return head;//这里的head还会一层一层的返回出去

        //2.准备向后递归调用（关于递归参数变化的操作）
        ListNode next = head.next;

        //3.递归
        ListNode reverseNext = reverseList2(next);//需要层层返回反转之前的最后一个ListNode

        //4
        next.next = head;//反转指针操作
        head.next = null;//是为了处理第一个元素的next指针的骚操作

        //5
        return reverseNext;//层层返回反转之前的最后一个ListNode
    }
}
/**
 * 总结：
 * 1.关于迭代法：
 *   *考虑到在改变next指针的时候会导致无法往后遍历的情况，我们需要在改变next指针之前，设置一个变量来记录当前的下一个节点。
 *   *在遍历之前先设置prev指针以方便修改指针指向
 * 2.关于递归：
 *   *递归是层层深入至最后一个节点，改变指针后，再层层浅出回第一个节点
 *   *这里有一个骚操作，就是在浅出时将当前的节点的next指针指向null，这样就巧妙的解决了浅出至第一个节点时的next指针问题
 */